package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.*;

/**
 * https://leetcode.cn/problems/subsets/description/?envType=study-plan-v2&envId=top-100-liked
 * 回溯方法通过
 *
 * @author yulongTian
 * @create 2024-07-01 13:44
 */
public class Test56 {
    public static void main(String[] args) {
        System.out.println(new Test56().subsets(new int[]{1, 2, 3}));
    }

    /**
     * 在原来的数组中不断追加下一个
     * 迭代法实现子集枚举
     * 通过
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> temp = res;
            int size = res.size();
            for (int j = 0; j < size; j++) {
                List<Integer> copy = new ArrayList<>(res.get(j));
                copy.add(nums[i]);
                temp.add(copy);
            }
            res = temp;
        }
        return res;
    }


//    /**
//     * 回溯方法
//     *
//     * @param nums
//     * @return
//     */
//    public List<List<Integer>> subsets(int[] nums) {
//        List<List<Integer>> res = new ArrayList<>();
//        res.add(new ArrayList<>());
//        Stack<Integer> stack = new Stack<>();
//        backtrack(nums, stack, res, 0);
//        return res;
//    }
//
//    public void backtrack(int[] nums, Stack<Integer> output, List<List<Integer>> res, int first) {
//        // 所有数都填完了
//        if (first == nums.length) {
//            return;
//        }
//        for (int i = first; i < nums.length; i++) {
//            // 动态维护数组
//            output.push(nums[i]);
//            res.add(new ArrayList<>(output));
//            // 继续递归填下一个数
//            backtrack(nums, output, res, i + 1);
//            // 撤销操作
//            output.pop();
//        }
//    }

}
